1. Field of Invention
The present invention relates generally to database systems More particularly, the present invention relates to a storage management technique which reduces the path lengths associated with allocating and freeing storage by implementing a push-only stack.
2. Description of the Related Art
Within any computing system, the amount of memory available for data storage purposes is typically limited. As such, storage management components or subsystems are often included within the computing system to manage the allocation and deallocation of memory space. Such storage management components provide general-purpose support for arbitrary usages of storage in which the storage management components have substantially no knowledge of the semantics of the data that consumes the storage.
A storage management system may generally be contained within an application server or system, a database system, or an operating system. FIG. 1 is a diagrammatic representation of a typical system which uses a storage management system. A system 100 includes a client 104, an application server 108, and a database system 110. Client 104, which may include a web browser 106, communicates with application server 108, or a middle tier, which may contain a web server (not shown). When client 104 communicates with application server 108, application server 108 may access information associated with database system 110. Typically, client 104, application server 108, and database system 110 are in communication over a network.
While client 104 and application server 108 may each have an associated operating system (not shown) within which a general-purpose storage management system may be contained, such storage management systems may allow storage to be consumed within client 104 and application server 108. Typically, the performance of such storage management systems may greatly affect the overall performance of their associated systems, i.e., client 104 and application server 108.
For procedural computing languages such as the C language, storage is typically allocated dynamically for data that is not understood at compile time, e.g., through calls to an operating system service or an application programming interface. The dynamically allocated storage may be allocated from application address space, which may be part of a run-time heap, as will be appreciated by those skilled in the art FIG. 2 is a diagrammatic representation of an application address space. An application address space 200, which maybe managed by an operating system, is typically contained within virtual storage and is partitioned. Virtual storage is generally a resource that is available to a process at run-time, and is located in real storage, e.g., random access memory (RAM), and partially located in auxiliary storage, e.g., disk space.
Executable code 204, which includes threads 220, may be included in application address space 200. Threads 220 are generally associated with concurrent independent tasks 224 or work each with their own storage requirements in a storage heap 208. As will be appreciated by those skilled in the art, dynamic storage occurs in storage heap 208. Application address space 200 also includes stack storage 212 and static storage 216.
When storage heap 208 fills up, i.e., when it is no longer possible to allocate storage in storage heap 208, then a garbage collection process is typically performed to free space within storage heap 208. In order for garbage collection to occur, tasks 224 include accounting information relating to garbage collection processes.
In a typical system, an average of approximately 100 storage allocations or deallocations per second may be considered to be a relatively low number of storage allocations and deallocations. However, at a cost of approximately five hundred to approximately a thousand instructions per storage allocation or deallocation, the number of instructions which execute each second with respect to storage allocations and deallocations may be substantial. That is, the path length associated with each storage allocation or deallocation may be in the range of approximately five hundred to approximately one thousand instructions. As such, when an operating system is required to grow virtual storage through additional page and segment table entries, the number of instructions to be executed may result in such a process being relatively expensive. In high volume transaction processing environments where path length is critical, the high number of instructions to be executed may significantly degrade the overall performance of a system. By way of example, the performance associated with Java Database Conductivity (JDBC) systems such as an Oracle JDBC Driver, available commercially from Oracle Corporation of Redwood Shores, Calif., may be compromised when the number of allocations or deallocations per unit of time is substantial.
Reducing the path length associated with storage allocations and deallocations may improve the overall performance of a system, particularly when the system is a high volume transaction processing system. One approach to reducing the path length associated with storage allocations and deallocations may include implementing an overall storage pool system. FIG. 3 is a diagrammatic representation of an overall storage pool system. An overall storage pool system 300, which is located in virtual memory, includes storage pools 308. A first storage pool 308a is arranged to store data of a first type and, hence, has semantics which support data of the first type. Similarly, a second storage pool 308b is arranged to store data of a second type, and has semantics which support data of the second type.
By providing different storage pools, the number of machine instructions for each storage type may be substantially optimized with respect to an appropriate storage pool 308. For example, if it is known that data of a first type is to be stored within first storage pool 308a, then the number of instructions needed to store data of the first type may be optimized accordingly. When data is needed dynamically by code 304, a storage management algorithm may access storage pools 308 to access the data.
Storage pools 308 may often be of a fixed size, i.e., storage pool 308a is often of substantially the same size as storage pool 308b, although the size of individual storage pools 308 may differ based upon the size of data items to be stored. The use of storage pools 308 of a fixed size is generally inefficient, as one storage pool 308 may be completely full, while another storage pool 308 may be relatively empty. Once a storage pool 308 for a data type is full, e.g., when storage pool 308a for a first data type is full, another storage pool 308 is typically allocated to store data of the first type. Allocating an additional storage pool 308 may be relatively expensive. In addition, allocating an additional storage pool 308 while other storage pools 308 such as storage pool 308b for a second data type remain relatively unused is generally a waste of storage.
At least some of the instructions associated with storage allocation and deallocation are related to tracking which allows ownership of data to be determined. For instance, allocating storage associated with procedural languages substantially requires that the allocated storage be accounted for by the owner of the storage such that the allocated storage may be deallocated, or freed, at a later time. That is, information relating to an owner of data that is stored, a location at which the data is stored, and garbage collection is tracked to enable the owner to later free the used storage space for other uses. The overhead associated with tracking, i.e., maintaining tracking information, generally creates a significant performance penalty.
While the use of overall storage pool system 300 may reduce the number of instructions associated with storing data, overall storage pool system 300, as discussed above, may be expensive as storage space associated with storage pools 308 may be used inefficiently, e.g., when one type of data is much more prevalent than another type of data. Further, although the number of instructions which are needed to store data in storage pools 308 may be lower than the number of instructions to store data into a storage heap such as storage heap 208 of FIG. 2, the number of instructions is still relatively high, as instructions associated with tracking stored data are still needed.
Therefore, what is needed is a storage management system and method which enables storage to be allocated and deallocated without requiring a relatively high number of instructions to be executed. More specifically, what is desired is a system which reduces the path length associated with dynamically storing data in virtual storage.
The present invention relates to dynamically allocating space within virtual memory at run-time while substantially minimizing an associated path length. According to one aspect of the present invention, a method for allocating virtual storage associated with a computer system includes creating a first linear space, allocating a unit of storage space within the first linear space, and writing a first set of information into the unit of storage space such that the first set of information is substantially not tracked. The first linear space supports allocation of storage space therein, and includes a first pointer that is arranged to identify a current location within the first linear space. The unit of storage which is allocated is associated with the current location. Finally, the method includes moving the first pointer in the first linear space to identify a second location within the first linear space. The first pointer moves in the first linear space in substantially only a top-to-bottom direction. In one embodiment, the unit of storage space within the first linear space is arranged not to be freed or reclaimed.
In another embodiment, the size of the first linear space is estimated through determining lifetimes and attributes of substantially all information that is expected to be written into the first linear space. In such an embodiment, lifetimes and attributes of substantially all the information to be written into the first linear space are similar.
Dynamically allocating and freeing storage in a linear space, e.g., a scratchpad, within virtual memory allows for a substantial reduction in path lengths associated with allocating and freeing storage and, further, increases a number of transactions which may be executed per unit of time. The reduction in path lengths is possible because scratchpad memory is substantially never freed. Since scratchpad memory is substantially never freed, there is effectively no need to maintain accounting information or tracking information when data representations are stored in a scratchpad. Therefore, the number of machine instructions associated with allocating and deallocating storage within the scratchpad may be significantly reduced.
According to another aspect of the present invention, a computing system includes a processor, a primary storage that is in communication with the processor, a secondary storage that is also in communication with the processor, and a virtual memory. The virtual memory includes at least a portion of the primary storage and at least a portion of the secondary storage, and also includes at least one scratchpad that functions as a push-only stack that supports dynamic storage allocation. The scratchpad is arranged not to be reclaimed or freed. In one embodiment, the scratchpad is allocated by an application which is executed by the processor to store data representations associated with the application.
These and other advantages of the present invention will become apparent upon reading the following detailed descriptions and studying the various figures of the drawings.